package ch20;
/**
 * Write a method to count the number of 2s between 0 and n.
 * @author Ray
 *
 */
public class ch20_4 {
	
	public static int count2_recursive(int n){
		if(n==0) return 0;
		//f(345) = 3*f(99)+f(45)+100
		
		int power = 1;
		while(10*power<n)
			power *= 10;
		int first = n/power;
		int remain = n%power;
		
		//count 2s for first digits, all the 200~299 have 2 for first digits
		int twoFirst = 0;
		if(first>2) twoFirst +=power;
		else if(first==2) twoFirst +=remain+1;
		
		int twoRemain = first * count2_recursive(power-1) + count2_recursive(remain);
		return twoFirst+twoRemain;
	}
	
	
	public static int count2_iterate(int n){
		int ret=0,cur_digit = 0;
		//pow_of_10 = 1,10,100...
		int position = 0, pow_of_10 = 1, seen = 0;
		int cur = n;
		while(cur>0){
			cur_digit = cur % 10;
			//number of 2s between 0~10 is 1
			//0~100 is 20
			//0~1000 is 300
			//0~10000 is 4000
			ret += cur_digit * position * (pow_of_10 / 10);
			if(cur_digit==2)
				ret += seen+1;
			else if(cur_digit>2)
				ret += pow_of_10;
			
			seen += pow_of_10*cur_digit;
			pow_of_10 *=10;
			++position;
			cur = cur/10;
		}
		return ret;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int test = 10000;
		System.out.println("The number of 2s between 0 and "+test+" is:");
		System.out.println(count2_recursive(test));
		System.out.println(count2_iterate(test));
	}

}
